package Year22_Month06.day20;

import java.util.ArrayList;
import java.util.List;

public class 二叉搜索树中的众数 {
    //这道题的话我唯一的想法就是遍历二叉搜索树，然后用哈希表保存对应关系
    //或者这样搞，我不用数组来维护，我用两个数字来进行维护
    int maxNum;//记录当前出现最多的次数
    int num;//因为中序遍历数组的众数一定是一个连续的数组，所以如果num是记录当前数字的
    int count;//记录当前数字出现的次数
    List<Integer> list = new ArrayList<>();//用来记录出现次数最多的数字

    public int[] findMode(TreeNode root) {
        inOrder(root);
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    public void inOrder(TreeNode node){
        if(node == null) return;
        inOrder(node.left);
        solve(node);
        inOrder(node.right);
    }

    public void solve(TreeNode node){
        //首先就是要验证当前节点和记录的节点值是否相同
        if(node.val != num) {
            num = node.val;
            count = 1;
        }else {
            count++;
        }
        //然后根据信息决定是否要更新值
        if(count > maxNum){
            maxNum = count;
            list.clear();
            list.add(node.val);
        }else if(count == maxNum){
            list.add(node.val);
        }
    }
}

/*   错误代码

public void solve(TreeNode node){
        if(node.val != num) {
            num = node.val;
            count = 1;
            return;
        }
        count++;
        if(count > maxNum){
            maxNum = count;
            list.clear();
            list.add(node.val);
        }else if(count == maxNum){
            list.add(node.val);
        }
    }
}
 */
